package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author feizns
 * @since 2020/3/16
 */
public class VerticalTraversal {

    public static void main(String[] args) {
//        Map<Integer, Set<Integer>> ret = new HashMap<>();
//        Set<Integer> set = ret.getOrDefault(1, new TreeSet<>());
//        set.add(1);
//        System.out.println(ret);
        System.out.println(new VerticalTraversal().verticalTraversal(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(3);
        ret.left = new TreeNode(9);
        ret.right = new TreeNode(20);
        ret.right.left = new TreeNode(15);
        ret.right.right = new TreeNode(7);
        return ret;
    }

    //x轴 => 深度 => 具体值
    Map<Integer, Map<Integer, Set<Integer>>> xMap = new TreeMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        return xMap.entrySet().stream().map(m -> m.getValue().values().stream().flatMap(Set::stream).collect(Collectors.toList())).collect(Collectors.toList());
    }

    private void dfs(TreeNode root, int x, int d) {
        if ( root != null ) {
            Map<Integer, Set<Integer>> levels = xMap.getOrDefault(x, new TreeMap<>());
            Set<Integer> values = levels.getOrDefault(d, new TreeSet<>());
            values.add(root.val);
            levels.put(d, values);
            xMap.put(x, levels);
            dfs(root.left, x - 1, d + 1);
            dfs(root.right, x + 1, d + 1);
        }
    }

//    public List<List<Integer>> verticalTraversal(TreeNode root) {
//        verticalTraversal(root, 0);
//        return ans;
//    }
//
//    List<List<Integer>> ans = new LinkedList<>();
//
//    private void verticalTraversal(TreeNode root, int index) {
//        if ( root != null ) {
//            if ( index < 0 || index == ans.size() ) {
//                index = index < 0 ? 0 : index;
//                ans.add(index, new LinkedList<>());
//            }
//            int size = ans.size();
//            ans.get(index).add(root.val);
//            verticalTraversal(root.left, index - 1);
//            verticalTraversal(root.right, index + ans.size() - size + 1);
//        }
//    }

}
